//Given an integer array nums of length n where all the integers of nums are in 
//the range [1, n] and each integer appears once or twice, return an array of all 
//the integers that appears twice. 
//
// You must write an algorithm that runs in O(n) time and uses only constant 
//extra space. 
//
// 
// Example 1: 
// Input: nums = [4,3,2,7,8,2,3,1]
//Output: [2,3]
// 
// Example 2: 
// Input: nums = [1,1,2]
//Output: [1]
// 
// Example 3: 
// Input: nums = [1]
//Output: []
// 
// 
// Constraints: 
//
// 
// n == nums.length 
// 1 <= n <= 10⁵ 
// 1 <= nums[i] <= n 
// Each element in nums appears once or twice. 
// 
//
// Related Topics 数组 哈希表 👍 709 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class P442FindAllDuplicatesInAnArray{
    //2023-05-13 10:44:59
    //Find All Duplicates in an Array
    //编号：[442]
    
    public static void main(String[] args) {

        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
static class Solution {
        public static List<Integer> P442FindAllDuplicatesInAnArray(int[] nums) {
            List<Integer> result = new ArrayList<>();
            int[] temp = new int[nums.length];
            for (int num : nums) {
                if (temp[num - 1] != 0) {
                    result.add(num);
                } else {
                    temp[num - 1] = num;
                }
            }
            return result;
        }

        public static void main(String[] args) {
            System.out.println(P442FindAllDuplicatesInAnArray(new int[]{1, 2, 2}));

        }
}
//leetcode submit region end(Prohibit modification and deletion)

}